/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.algorithm
 * author:David
 * Date:2015年6月16日下午4:14:07
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.algorithm;

/**
 * 递归算法回顾
 * @author David
 * @since 2015年6月16日 下午4:14:07
 * @version 
 * @since JDK 1.6
 */
public class Recursion {
	
	public static void main(String[] args) {
//		System.out.println(factorial(5));
		Recursion recursion=new Recursion();
//		recursion.hanio(1, 'x', 'y', 'z');
		recursion.hanio(3, 'x', 'y', 'z');
//		recursion.codingNBool(new int[1], 0);
//		recursion.codingNBool(new int[2], 1);
//		recursion.codingNBool(new int[4], 2);
	}
	
	
	/**
	 * 求n！=[1 when n=0,n(n-1)! when n>0]
	 * @param n
	 * @return
	 */
	static int factorial(int n){
		if (n==0) {
			return 1;
		}else{
			return n*factorial(n-1);
		}
	}
	
	/**
	 * 汉诺塔问题求解
	 * 把塔座x上的所有盘子移动到塔座z上并保持原来的顺序，
	 * 在移动过程中要满足：在塔座之间一次只能移动一个盘子并且在任何时候
	 * 大盘子都不能放到小盘子上
	 * @param n --n个大小不一的盘子
	 * @param x --塔座x
	 * @param y --塔座y
	 * @param z --塔座z
	 */
	void hanio(int n,char x,char y,char z){
		if(n==1){
			move(x,n,z);
		}else{
			hanio(n-1,x,z,y);
			move(x,n,z);
			hanio(n-1, y, x, z);
		}
	}
	/**
	 * 把x上n个盘子移动到z上
	 * @param x
	 * @param n
	 * @param z
	 */
	private void move(char x, int n, char y) {
		System.out.println("Move "+n+" from "+x+" to "+y);
	}
	
	/**
	 * 输出n位布尔量的所有组合算法
	 * @param bool 数组bool来存放n位组合的每一个分量
	 * @param n 正整数
	 */
	void codingNBool(int[]bool,int n){
		if(n==0){
			bool[n]=0;
			printBool(bool);
			bool[n]=1;
			printBool(bool);
		}else{
			bool[n]=0;
			codingNBool(bool, n-1);
			bool[n]=1;
			codingNBool(bool, n-1);
		}
	}


	/**
	 * 打印所有可能的布尔组合
	 * @param bool
	 */
	private void printBool(int[] bool) {
		for(int i=0;i<bool.length;i++){
			System.out.print(bool[i]);
		}
		System.out.println();
	}
	
	

}
